package priv.sort.radix;

import java.util.ArrayList;
import java.util.List;

public class RadixSort {
    public static void sort(int[] arr) {
        if (arr.length < 2) return;
        int max = 0;
        // 获取最大值
        for (int value : arr) {
            if (value > max) {
                max = value;
            }
        }
        // 计算位数
        int n = 0;
        while (max != 0) {
            max /= 10;
            n++;
        }
        // 基数排序
        for (int i = 0; i < n; i++) {
            List<List<Integer>> radix = new ArrayList<>();
            // 初始化
            for (int j = 0; j < 10; j++) {
                radix.add(new ArrayList<>());
            }
            // 按位分组添加到radix
            for (int value : arr) {
                int digit = (value / (int) Math.pow(10, i)) % 10;
                radix.get(digit).add(value);
            }
            // 按位排序，输出返回到原数组
            int index = 0;
            for (List<Integer> list : radix) {
                for (int value : list) {
                    arr[index++] = value;
                }
            }
        }
    }
}
